The invention relates to a signal processing apparatus and methods for performing Fourier analysis and synthesis.
The Arithmetic Fourier Transform (AFT) is an algorithm for accurate high speed Fourier analysis and narrow-band filtering. The arithmetic computations in the AFT can be performed in parallel. Except for a small number of scalings in one stage of the computation, only multiplications by 0, +1 and -1 are required. Thus, the accuracy of the AFT is limited only by the analog-to-digital conversion of the input data, not by accumulation of rounding and coefficient errors as in the Fast Fourier Transform (FFT). Furthermore, the AFT needs no storage of memory addressing. These properties of the AFT make it very suitable for VLSI implementation of Fourier analysis.
In the early part of this century, a mathematician, H. Bruns, found a method for computing the Fourier series coefficients of a periodic function using Mobius inversion. Later in 1945, another mathematician, Aurel Wintner, reconsidered this technique and developed an arithmetic approach to ordinary Fourier series. Tufts later discovered the same algorithm and named it the Arithmetic Fourier Transform (AFT) and showed how parallel computations and efficient communication and control are built into the algorithm and pointed out its applications in fast Fourier analysis and signal processing using the AFT and used a simple interpolation scheme to realize the extended AFT. Relating thereto, Tufts described a signal processing apparatus for generating a Fourier transform of a signal using the AFT in U.S. Pat. No. 4,999,799, incorporated herein by reference.
Recently, a method of approximately realizing the inverse AFT by successive approximation has been proposed. This method is closely related to the least mean squares (LMS) successive approximation realization of the Discrete Fourier Transform (DFT). Using the adaptive method, only N time domain data samples are required and about N.sup.2 /3 frequency domain samples are obtained. This is in contrast with the original forward use of the AFT algorithm in which about N.sup.2 /3 time domain samples are required to compute N frequency domain samples. The computations involved in this sequential AFT method are the same as those in the AFT, namely, scaling by inverse-integer factors and accumulation. The number of iterations of this sequential method depends directly on the input data length N and there are difficulties about the convergence of this approximation process to a result which is consistent with a zero-padded DFT.
A unique apparatus and method for iteratively determining the inverse AFT is herein presented. The apparatus and method utilize an algorithm which uses a data block of N samples to iteratively compute a set of about N.sup.2 frequency samples. Each iteration uses the error information between the observed data and data synthesized using the original AFT algorithm. If started with a properly synthesized data vector, the calculation will converge and give the inverse AFT values at the Farey-fraction arguments which are consistent with the values given by a zero-padded DFT. Therefore, it effectively overcomes the difficulty of dense, Farey-fraction sampling iterative use of the AFT. Dense frequency domain samples are obtained without any interpolation or zero-padding. The implementation of this iterative apparatus and method also preserves the advantage of the AFT for VLSI implementation by using a permuted difference coefficient structure (PDC) to provide simple computation of the updated Fourier transform vector. PDC is based on the mathematical formulation known as Summation by Parts (SBP) which is a finite difference analog to the integration by parts reformulation of an integral found in any standard calculus book. The arithmetic computation of this iterative AFT has a high degree of parallelism and the resulting architecture is regular. Because of its simplicity, this iterative AFT apparatus and method could be of interest in many applications such as phase retrieval, two dimensional maximum entropy power spectral estimation and recursive digital filter design, where many Fourier transform and inverse Fourier transform calculations are required, realization of multichannel filters, and determination of direction of arrival of a signal using an array of antennas, or microphones or hydrophones. The iterative AFT apparatus and method may be used with the AFT in these applications to perform the Fourier analysis efficiently.